// 二叉树的中序遍历

package Leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
// import java.util.Stack;

//   Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution94_1 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            // 向左走到尽头
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 栈顶元素出栈，并访问
            root = stack.pop();
            result.add(root.val);
            // 获得栈顶元素的右子树，如果为null，则在下一次循环中栈顶元素会接着出栈直至找到有右子树的栈顶
            root = root.right;
        }
        return result;
    }
}


// 递归法
class Solution094_2 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Inorder(result, root);
        return result;
    }

    public void Inorder(List<Integer> result, TreeNode root) {
        if (root != null) {
            Inorder(result, root.left);
            result.add(root.val);
            Inorder(result, root.right);
        }
    }
}


// Mirrors解法，以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
class Solution94_3 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode currentRoot = root; // 当前开始遍历的结点
        TreeNode cur = null; // 记录当前结点的左子树

        while (currentRoot != null) {
            cur = currentRoot.left;
            // 如果当前结点有左子树
            if (cur != null) {
                // 左子树的右节点不为空且还没有与根结点建立连接
                while (cur.right != null && cur.right != currentRoot)
                    cur = cur.right;
                // 此时要么cur.right==null,要么cur.right==currentRoot
                // 这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
                if (cur.right == null) {
                    cur.right = currentRoot;
                    currentRoot = currentRoot.left;
                    continue;
                }
                // 当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，
                // 同时在回到根结点的时候我们应该已经处理完左子树的最右侧节点了，把路断开。
                else {
                    cur.right = null;
                }
            } // if
            list.add(currentRoot.val);
            // 不是回到上一个根结点，而是到当前root的右子树
            currentRoot = currentRoot.right;
        } // while

        return list;
    }
}
